package 牛客.动态规划;

public class BM65最长公共子串_二 {
    //本题的公共子串要求不连续，并且返回最长公共子串的字符串
    //不同于 BM66
    public String LCS (String s1, String s2) {
        // write code here
        //动态规划，dp先用来求公共子串的最长长度
        int[][] dp=new int[s1.length()+1][s2.length()+1];
        //dp[i][j]代表 s1中下标从[0,i-1] 和 s2中下标从[0,j-1]，它两的公共子串的最长长度

        for (int i = 1; i <s1.length()+1 ; i++) {
            for (int j = 1; j <s2.length()+1 ; j++) {
                if (s1.charAt(i-1)==s2.charAt(j-1)) {
                    dp[i][j]=dp[i-1][j-1]+1;
                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);//在上边或左边挑选最大值填入
                }
            }
        }
        if (dp[s1.length()][s2.length()]==0) {
            return "-1";
        }

        StringBuilder sb=new StringBuilder();
        //根据dp把公共子串倒着拼接出来
        int n=s1.length(); //n行
        int m=s2.length(); //m列
        while (n>0 && m>0) {
            if (s1.charAt(n-1)==s2.charAt(m-1)) {
                sb.append(s1.charAt(n-1));
                n--;
                m--;
            }else {
                if (dp[n-1][m]>dp[n][m-1]) {
                    n--;
                }else {
                    m--;
                }
            }
        }
        return sb.reverse().toString();
    }

}
